The present invention generally relates to the design of electrical connections, or interconnects, situated within integrated circuits, and more particularly, to a simultaneous path optimization (SPO) system and method for automatically and efficiently determining where to insert repeaters (buffers or drivers) within interconnects of an integrated circuit during the design of the interconnects in order to ultimately reduce signal propagation delays in the interconnects.
As operating frequencies increase to hundreds of megahertz (MHz) for multimedia processors and application specific integrated circuits (ASICs) and increase to around a gigahertz (GHz) for the next generation of central processing units (CPUs), the global electrical signals, for example, reset, stall, clock, and control, have less time to traverse an integrated circuit (IC) on a microchip (chip) due to reduced cycle time. The problem is compounded even further as IC chips get larger and larger. Therefore, global signals often exhibit larger than desirable propagation delays, and the circuits need to be optimized so that signals meet timing specifications.
Generally, the propagation delay associated with a signal, or the time necessary for the signal to propagate from one point to another on a chip, is caused by resistances and/or capacitances imposed upon the signal path, and is sometimes referred to as xe2x80x9cRC delay.xe2x80x9d These resistances and capacitances also degrade the signal (decrease its rising/falling slope) as the signal propagates along a connection, which is another undesirable deleterious effect.
Many diverse approaches to this problem have been developed by researchers and published in the past few years. Consider the following, as examples: (1) N. Menezes, R. Baldick, and L. T. Pileggi, xe2x80x9cA Sequential Quadratic Programming Approach to Concurrent Gate,xe2x80x9d Department of Electrical and Computer engineering, University of Texas at Austin, ICCAD, November 1995; (2) J. Lillis, C. K. Cheng, and T. T. Lin, xe2x80x9cOptimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model,xe2x80x9d University of California, San Diego, Calif., ICCAD, November 1996; (3) J. Cong, and C. K. Koh, xe2x80x9cSimultaneous Driver and Wire Sizing for Performance and Power Optimization,xe2x80x9d University of California, Los Angeles, Calif., IEEE, Transactions on Very Large Scale Integration Systems, Vol. 2, No. 4, December 1994; and (4) L. P. Ginneken, xe2x80x9cBuffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay,xe2x80x9d IBM, NY, IEEE International Symposium on Circuits and Systems, 1990.
One effective technique in reducing the delay of a signal involves inserting a xe2x80x9crepeaterxe2x80x9d (also referred to in the art as a xe2x80x9cdriverxe2x80x9d or xe2x80x9cbufferxe2x80x9d) along the signal path. A repeater is generally a circuit, for example, an inverter or set of cascaded inverters, that reduces the RC delay and slope degradation of the propagated signal. Historically, determining where to insert repeaters has been accomplished by creating and analyzing models of IC circuits. A mathematical algorithm known as xe2x80x9cElmorexe2x80x9d has been used in the past to compute RC delays before and after introduction of repeaters in a circuit. The Elmore algorithm is described in detail in L. P. Ginneken, xe2x80x9cBuffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay,xe2x80x9d IBM, NY, IEEE International Symposium on Circuits and Systems, 1990. However, this process is time consuming and has traditionally been performed by having an engineer or designer review circuit models and determine where to insert repeaters.
Software tools for modeling and simulating circuits are well known in the art. Well known delays simulators (or calculators) include, for example, SPICE, and OPTspice (available from Hewlett-Packard Company, U.S.A.). Although the foregoing software programs can be used for modeling and simulations, they do not automatically determine where and to what extent repeaters should be placed within a circuit.
Thus, a heretofore unaddressed need exists in the industry for a way to automatically and efficiently determine where to insert repeaters when designing an IC in order to reduce signal propagation delays in the IC.
A simultaneous path optimization (SPO) system (and associated method) automatically and efficiently determines where to insert repeaters (or buffers or drivers) within interconnects of an integrated circuit (IC) during the design of the interconnects in order to ultimately reduce signal propagation delays in the interconnects. The SPO system is implemented in software, hardware, or a combination thereof, but is preferably implemented as a software tool executed by a computer system that is used in connection with one or more conventional delay simulators (e.g., the SPICE program), also in the form of software that is executed by a computer system.
In architecture, the SPO system is designed as follows. The SPO system is designed to receive or obtain a description, or netlist, of an electrical network. The netlist indicates a source node, a plurality of sink nodes, a plurality of electrical branches connecting the source node with each the sink node, a plurality of resistances associated respectively with the branches, a plurality of capacitances associated respectively with the branches, and a plurality of timing constraints associated respectively with the branches. Each the timing constraint represents a maximum propagation time delay between the source and a respective one of the sinks.
The SPO system causes the netlist to be simulated using a delay simulator. Although not required to practice the present invention, the SPO system defines and utilizes a slack parameter. The SPO system determines a slack parameter for each branch of the network. The slack parameter is computed for each branch by mathematically combining (e.g., subtracting) a signal propagation delay associated the each branch and a timing constraint associated with each branch. The SPO system determines a main branch in the network as one of the branches that exhibits the largest one of the slack parameters. The SPO system produces a total slack parameter by mathematically combining (e.g., adding) the slack parameters. The SPO system determines how many of the repeaters, if any, should be inserted in at least one side branch extending from the main branch by simulating at least one repeater in at least one side branch and determining whether the total slack parameter decreases by insertion of the at least one repeater. The SPO system determines how many of the other repeaters, if any, should be inserted along the main branch using a first delay simulator and simulating at least one other repeater. The SPO system determines a position for each of the other repeaters using a second delay simulator and simulating the other repeaters. Finally, the SPO system outputs the repeater locations and connectivity. The connectivity is generally a description as to what circuit elements each repeater is connected at its input and output ports.
Although not limited to this implementation, in the preferred embodiment, the aforementioned first delay simulator uses either a fast balanced segment delay process/system or an exhaustive search process, and the aforementioned second delay simulator uses a slower balanced segment delay process. In a sense, this overall process can be viewed as having a course adjustment part and a fine adjustment part, which achieves speedy and accurate results.
The invention may also be viewed as providing one or more methods for determining where to insert repeaters when designing an integrated circuit in order to reduce signal propagation delays in the integrated circuit. In this regard, one of the methods can be broadly summarized by the following steps: (a) obtaining a description of an electrical network; (b) determining a main branch in said network from said description based upon signal propagation delays associated with respective branches of said network; (c) simulating at least one repeater in at least one side branch extending from said main branch; (d) determining whether said at least one repeater should be inserted, where simulated, based upon said signal propagation delays associated with said branches; (e) simulating at least one other repeater along said main branch; and (f) determining whether said at least one other repeater should be inserted, where simulated, based upon said signal propagation delays associated with said branches. Furthermore, the method may further include the following additional steps: determining how many more of the repeaters, if any, should be inserted in the side branches via simulation of at least one more repeater in the side branches; and determining a position for each of the additional repeaters.
Another method involves a balanced segment delay method. In this regard, this method can be summarized by the following steps: A balanced segment delay method for optimizing speed associated with a branch of a circuit, comprising the steps of: (a) obtaining a description of a branch; (b) inserting a repeater in said branch to create a configuration having first and second segments of the branch that are connected to respective first and second ports of the repeater; (c) simulating the configuration to determine first and second segment delays for the first and second segments respectively and an overall branch delay for the branch; (d) storing the overall branch delay; (e) determining which direction the repeater will be moved along the branch based upon the first and second segment delays; (f) moving the repeater in the configuration to reduce the size of one of the first and second segments, while increasing the size of the other one or the first and second segments; (g) repeating steps (c) through (f) until the first and second segment delays are equal within a predefined threshold; and (h) selecting a particular one of the configurations that exhibits a lowest overall branch delay.